package com.chj.zhongji.class09.test01;

//https://blog.csdn.net/zcz5566719/article/details/105910946
//https://blog.csdn.net/ZhEnG_jIe_YuAn/article/details/107302128
//https://blog.csdn.net/u011604049/article/details/107251040
//matrix = [
//
//[ 1, 5, 9],
//
//[10, 11, 13],
//
//[12, 13, 15] ], k = 8
//
//返回 13
public class Code04_TopKSumMatrix {

	public static class HeapNode {
		int row;
		int col;
		int value;

		public HeapNode(int row, int col, int value) {
			this.row = row;
			this.col = col;
			this.value = value;
		}
	}

	public static int[] TokSum(int[][] matrix, int k) {
		if (matrix == null || matrix.length == 0) {
			return new int[] {};
		}

		int rowl = matrix.length;
		int coll = matrix[0].length;
		int topK = Math.min(k, rowl * coll);

		HeapNode[] heap = new HeapNode[topK + 1];
		int heapSize = 0;

		int headRow = -1;
		int headCol = -1;
		int uRow = -1;
		int uCol = -1;
		int lRow = -1;
		int lCol = -1;

		boolean[][] set = new boolean[rowl][coll];

		int[] res = new int[topK];
		int resIndex = 0;
		heapInsert(heap, heapSize, 0, 0, matrix[0][0]);
		heapSize++;
		while (resIndex != topK) {
			HeapNode head = popHead(heap, heapSize);
			heapSize--;
			res[resIndex++] = head.value;
			headRow = head.row;
			headCol = head.col;

			uRow = headRow + 1;
			uCol = headCol;
			if (uRow < rowl && !set[uRow][uCol]) {
				heapInsert(heap, heapSize, uRow, uCol, matrix[uRow][uCol]);
				heapSize++;
				set[uRow][uCol] = true;
			}

			lRow = headRow;
			lCol = headCol + 1;
			if (lCol < coll && !set[lRow][lCol]) {
				heapInsert(heap, heapSize, lRow, lCol, matrix[lRow][lCol]);
				heapSize++;
				set[lRow][lCol] = true;
			}
		}

		return res;
	}

	public static void heapInsert(HeapNode[] heap, int index, int row, int col, int value) {
		HeapNode newNode = new HeapNode(row, col, value);
		heap[index] = newNode;
		int parent = (index - 1) / 2;
		while (heap[index].value < heap[parent].value) {
			swap(heap, index, parent);
			index = parent;
			parent = (index - 1) / 2;
		}
	}

	public static void heapify(HeapNode[] heap, int index, int size) {
		int left = index * 2 + 1;
		int right = left + 1;
		int largest = index;
		while (left < size) {

			if (right < size && heap[left].value > heap[right].value) {
				largest = right;
			} else {
				largest = left;
			}

			largest = heap[index].value > heap[largest].value ? largest : index;

			if (largest == index) {
				break;
			}
			swap(heap, largest, index);
			index = largest;
			left = index * 2 + 1;
			right = left + 1;
		}
	}

	public static HeapNode popHead(HeapNode[] heap, int size) {
		HeapNode res = heap[0];
		swap(heap, 0, size - 1);
		size--;
		heap[size] = null;
		heapify(heap, 0, size);
		return res;
	}

	public static void swap(HeapNode[] heap, int index1, int index2) {
		HeapNode temp = heap[index1];
		heap[index1] = heap[index2];
		heap[index2] = temp;
	}

	public static void main(String[] arg) {
		int[][] matrix = new int[][] { { 1, 5, 9 }, { 10, 11, 13 }, { 12, 13, 15 } };
		int k = 8;
		int[] res = TokSum(matrix, k);
		for (int i = 0; i < res.length; i++) {
			System.out.print(res[i] + " ");
		}
	}
}
